Existing pairing based cryptographic systems use Weil or Tate pairings evaluated at points on an abelian variety, for example, an elliptic curve. For a fixed natural number m, the Weil pairing em is a bilinear map that takes as input two m-torsion points on the elliptic curve, and outputs an m th root of unity. For instance, for a fixed natural number m, the Weil pairing em is a bilinear map that takes as input two m-torsion points on an elliptic curve, and outputs an mth root of unity.